/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName   : Leetcode0073 
 * @author      : ganwei 
 * @date        : 2020年5月25日
 * @Description : Leetcode0073 矩阵置零
 */
public class Leetcode0073 {
	/**
	 * -解题思路,空间复杂度O(M+N)
	 */
    public void setZeroes(int[][] matrix) {
    	if(matrix.length <= 0) {
    		return;
    	}
    	int r = matrix.length;
    	int c = matrix[0].length;
    	Set<Integer> rows = new HashSet<Integer>();
    	Set<Integer> cols = new HashSet<Integer>();
    	for(int i = 0; i < r; i++){
    		for(int j = 0; j < c; j++){
    			if(matrix[i][j] == 0){
    				rows.add(i);
    				cols.add(j);
    			}
    		}
    	}
    	
    	for(int row : rows){
    		for(int i = 0; i < c; i++){
    			matrix[row][i] = 0;
    		}
    	}
    	for(int col : cols){
    		for(int i = 0; i < r; i++){
    			matrix[i][col] = 0;
    		}
    	}
    }
	/**
	 * -解题思路,空间复杂度常数级
	 */
    public void setZeroes_1(int[][] matrix) {
    	if(matrix.length <= 0) {
    		return;
    	}
    	int r = matrix.length;
    	int c = matrix[0].length;
    	
    	boolean row0_flag = false;
    	boolean col0_flag = false;
    	//第一行是否有0 
    	for(int i = 0; i < c; i++){
    		if(matrix[0][i] == 0) {
    			row0_flag = true;
    			break;
    		}
    	}
    	//第一列是否有0
    	for(int i = 0; i < r; i++){
    		if(matrix[i][0] == 0) {
    			col0_flag = true;
    			break;
    		}
    	}
    	//把第一行、第一列作为标记位
    	for(int i = 1; i < r; i++){
    		for(int j = 1; j < c; j++){
    			if(matrix[i][j] == 0){
    				matrix[i][0] = 0;
    				matrix[0][j] = 0;
    			}
    		}
    	}
    	//置0
    	for(int i = 1; i < r; i++){
    		for(int j = 1; j < c; j++){
    			if(matrix[i][0] == 0 || matrix[0][j] == 0){
    				matrix[i][j] = 0;
    			}
    		}
    	}
        if (row0_flag) {
            for (int j = 0; j < c; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < r; i++) {
                matrix[i][0] = 0;
            }
        } 

    }
}
